//
// (C) Copyright 2009 Irantha Suwandarathna (irantha@gmail.com)
// All rights reserved.
//

/* Copyright (c) 1995-2000, The Hypersonic SQL Group.
 * All rights reserved.
 *
 * Redistribution and use _in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions _in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer _in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the Hypersonic SQL Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * This software consists of voluntary contributions made by many individuals
 * on behalf of the Hypersonic SQL Group.
 *
 *
 * For work added by the HSQL Development Group:
 *
 * Copyright (c) 2001-2008, The HSQL Development Group
 * All rights reserved.
 *
 * Redistribution and use _in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions _in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer _in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the HSQL Development Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using EffiProzDB.Lib;


namespace EffiProzDB
{


    // fredt@users 20010701 - patch 1.6.1 by hybris
    // basic implementation of LIMIT n m
    // fredt@users 20020130 - patch 471710 by fredt - LIMIT rewritten
    // for SELECT LIMIT n m DISTINCT
    // fredt@users 20020221 - patch 513005 by sqlbob@users (RMP)
    // type and logging attributes of sIntotable
    // fredt@users 20020230 - patch 495938 by johnhobs@users - GROUP BY order
    // fred@users 20020522 - patch 1.7.0 - aggregate functions with DISTINCT
    // rougier@users 20020522 - patch 552830 - COUNT(DISTINCT)
    // fredt@users 20020804 - patch 580347 by dkkopp - view speedup
    // tony_lai@users 20021020 - patch 1.7.2 - improved aggregates and HAVING
    // boucherb@users 20030811 - patch 1.7.2 - prepared statement support
    // fredt@users 20031012 - patch 1.7.2 - better OUTER JOIN implementation
    // fredt@users 20031012 - patch 1.7.2 - SQL standard ORDER BY with UNION and other set queries
    // fredt@users 200408xx - patch 1.7.2 - correct evaluation of the precedence of nested UNION and other set query

    /**
     * The compiled representation of an SQL SELECT.
     *
     * Extended _in successive versions of HSQLDB.
     *
     * @author Thomas Mueller (Hypersonic SQL Group)
     * @version 1.8.0
     * @since Hypersonic SQL
     */
    public class Select
    {

        public bool isDistinctSelect;
        public bool isAggregated;
        private bool isGrouped;
        private HashSet<string> groupColumnNames;
        public TableFilter[] tFilter;
        public Expression limitCondition;
        public Expression queryCondition;     // null means no condition
        public Expression havingCondition;    // null means none
        public Expression[] exprColumns;        // 'result', 'group' and 'order' columns
        public int iResultLen;         // number of columns that are 'result'
        public int iGroupLen;          // number of columns that are 'group'
        public int iHavingLen;         // number of columns that are 'group'
        public int iOrderLen;          // number of columns that are 'order'
        public int[] sortOrder;
        public int[] sortDirection;
        public bool sortUnion;          // if true, sort the result of the full union
        public HsqlNameManager.HsqlName sIntoTable;         // null means not select..into
        public int intoType;
        public Select[] unionArray;         // only set _in the first Select _in a union chain
        public int unionMaxDepth;      // max unionDepth _in chain
        public Select unionSelect;        // null means no union select
        public int unionType;
        public int unionDepth;
        public  const int NOUNION = 0,
                              UNION = 1,
                              UNIONALL = 2,
                              INTERSECT = 3,
                              EXCEPT = 4;
        private bool simpleLimit;        // true if maxrows can be uses as is
        public Result.ResultMetaData resultMetaData;
        public Dictionary<int, object> asteriskPositions;

        /**
         * Experimental.
         *
         * Map the column aliases to expressions _in order to resolve alias names
         * _in WHERE clauses
         *
         */
        public Dictionary<string, Expression> getColumnAliases()
        {

            Dictionary<string, Expression> aliasMap = new Dictionary<string, Expression>();

            for (int i = 0; i < iResultLen; i++)
            {
                string alias = exprColumns[i].getAlias();

                if (alias != null)
                {
                    aliasMap.Add(alias, exprColumns[i]);
                }
            }

            return aliasMap;
        }

        /**
         * Method declaration
         *
         *
         * @ 
         */
        public void resolve(Session session)
        {

            resolveTables();
            resolveTypes(session);
            setFilterConditions(session);
        }

        /**
         * Method declaration
         *
         *
         * @ 
         */
        private void resolveTables()
        {

            // replace the aliases with expressions
            for (int i = iResultLen; i < exprColumns.Length; i++)
            {
                if (exprColumns[i].getType() == Expression.COLUMN)
                {
                    if (exprColumns[i].joinedTableColumnIndex == -1)
                    {
                        bool descending = exprColumns[i].isDescending();

                        exprColumns[i] =
                            exprColumns[i].getExpressionForAlias(exprColumns,
                                iResultLen);

                        if (descending)
                        {
                            exprColumns[i].setDescending();
                        }
                    }
                }
                else
                {
                    exprColumns[i].replaceAliases(exprColumns, iResultLen);
                }
            }

            if (queryCondition != null)
            {
                queryCondition.replaceAliases(exprColumns, iResultLen);
            }

            int len = tFilter.Length;

            for (int i = 0; i < len; i++)
            {
                resolveTables(tFilter[i]);
            }
        }

        /**
         * Converts the types of the columns _in set operations to those _in the first
         * Select.
         */
        public void resolveUnionColumnTypes()
        {

            if (unionSelect != null)
            {
                if (unionSelect.iResultLen != iResultLen)
                {
                    throw Trace.error(Trace.COLUMN_COUNT_DOES_NOT_MATCH);
                }

                for (int i = 0; i < iResultLen; i++)
                {
                    Expression e = exprColumns[i];

                    if (!e.isTypeEqual(unionSelect.exprColumns[i]))
                    {
                        unionSelect.exprColumns[i] =
                            new Expression(unionSelect.exprColumns[i],
                                           e.getDataType(), e.getColumnSize(),
                                           e.getColumnScale());
                    }
                }
            }
        }

        /**
         * Sets the types of all the expressions that have so far resolved.
         *
         * @ 
         */
        public void resolveTypes(Session session)
        {

            int len = exprColumns.Length;

            for (int i = 0; i < len; i++)
            {
                exprColumns[i].resolveTypes(session);
            }

            if (queryCondition != null)
            {
                queryCondition.resolveTypes(session);
            }
        }

        public void resolveTablesUnion(TableFilter f)
        {

            if (unionArray == null)
            {
                resolveTables(f);
            }
            else
            {
                for (int i = 0; i < unionArray.Length; i++)
                {
                    unionArray[i].resolveTables(f);
                }
            }
        }

        /**
         * Resolves the tables for all the Expression _in the Select object
         * if it is possible to do so with the given TableFilter.
         *
         * @param f
         *
         * @ 
         */
        public void resolveTables(TableFilter f)
        {

            int len = exprColumns.Length;

            for (int i = 0; i < len; i++)
            {
                exprColumns[i].resolveTables(f);
            }

            if (queryCondition != null)
            {
                queryCondition.resolveTables(f);
            }
        }

        private void setFilterConditions(Session session)
        {

            if (queryCondition == null)
            {
                return;
            }

            for (int i = 0; i < tFilter.Length; i++)
            {
                tFilter[i].setConditions(session, queryCondition);
            }
        }

        /**
         * Check all Expression have resolved. Return true or false as a result.
         * Throw if false and check parameter is true.
         *
         * @ 
         */
        public bool checkResolved(bool check)
        {

            bool result = true;
            int len = exprColumns.Length;

            for (int i = 0; i < len; i++)
            {
                result = result && exprColumns[i].checkResolved(check);
            }

            if (queryCondition != null)
            {
                result = result && queryCondition.checkResolved(check);
            }

            if (havingCondition != null)
            {
                result = result && havingCondition.checkResolved(check);
            }

            for (int i = 0; i < tFilter.Length; i++)
            {
                if (tFilter[i].filterIndex == null)
                {
                    tFilter[i].filterIndex =
                        tFilter[i].filterTable.getPrimaryIndex();
                }
            }

            return result;
        }

        /**
         * Removes all the TableFilters from the Expressions.
         *
         * @ 
         */
        /*
            void removeFilters()   {

                int len = eColumn.Length;

                for (int i = 0; i < len; i++) {
                    eColumn[i].removeFilters();
                }

                if (eCondition != null) {
                    eCondition.removeFilters();
                }
            }
        */

        /**
         * Returns a single value result or throws if the result has more than
         * one row with one value.
         *
         * @param type data type
         * @param session context
         * @return the single valued result
         * @ 
         */
        public Object getValue(Session session, int type)
        {

            resolve(session);

            Result r = getResult(session, 2);    // 2 records are required for test
            int size = r.getSize();
            int len = r.getColumnCount();

            if (len == 1)
            {
                if (size == 0)
                {
                    return null;
                }
                else if (size == 1)
                {
                    Object o = r.rRoot.data[0];

                    return r.metaData.colTypes[0] == type ? o
                                                          : Column.convertObject(
                                                          o, type);
                }
                else
                {
                    throw Trace.error(Trace.CARDINALITY_VIOLATION_NO_SUBCLASS);
                }
            }

            HsqlException e =
                Trace.error(Trace.CARDINALITY_VIOLATION_NO_SUBCLASS);

            throw new HsqlInternalException(e);
        }

        /**
         * Resolves expressions and pepares thre metadata for the result.
         */
        public void prepareResult(Session session)
        {

            resolveAll(session, true);

            if (iGroupLen > 0)
            {    // has been set _in Parser
                isGrouped = true;
                groupColumnNames = new HashSet<string>();

                for (int i = iResultLen; i < iResultLen + iGroupLen; i++)
                {

                    //              MarcH: this is wrong for a CASE WHEN statement _in a SELECT CASE WHEN ...,<something aggregate> statement
                    //              collectColumnName collects no columns if exprColumns[i]'s expressiontype is Expression.CASEWHEN
                    //              collectAllColumnNames collects all columns used _in the CASE WHEN statement
                    //              exprColumns[i].collectColumnName(groupColumnNames);
                    exprColumns[i].collectAllColumnNames(groupColumnNames);
                }
            }

            int len = exprColumns.Length;

            resultMetaData = new Result.ResultMetaData(len);

            Result.ResultMetaData rmd = resultMetaData;

            // tony_lai@users having
            int groupByStart = iResultLen;
            int groupByEnd = groupByStart + iGroupLen;
            int orderByStart = groupByEnd + iHavingLen;
            int orderByEnd = orderByStart + iOrderLen;

            for (int i = 0; i < len; i++)
            {
                Expression e = exprColumns[i];

                rmd.colTypes[i] = e.getDataType();
                rmd.colSizes[i] = e.getColumnSize();
                rmd.colScales[i] = e.getColumnScale();

                if (e.isAggregate())
                {
                    isAggregated = true;
                }

                if (i >= groupByStart && i < groupByEnd
                        && !exprColumns[i].canBeInGroupBy())
                {
                    Trace.error(Trace.INVALID_GROUP_BY, exprColumns[i]);
                }

                if (i >= groupByEnd && i < groupByEnd + iHavingLen
                        && !exprColumns[i].isConditional())
                {
                    Trace.error(Trace.INVALID_HAVING, exprColumns[i]);
                }

                if (i >= orderByStart && i < orderByEnd
                        && !exprColumns[i].canBeInOrderBy())
                {
                    Trace.error(Trace.INVALID_ORDER_BY, exprColumns[i]);
                }

                if (i < iResultLen)
                {
                    rmd.colLabels[i] = e.getAlias();
                    rmd.isLabelQuoted[i] = e.isAliasQuoted();
                    rmd.schemaNames[i] = e.getTableSchemaName();
                    rmd.tableNames[i] = e.getTableName();
                    rmd.colNames[i] = e.getColumnName();

                    if (rmd.isTableColumn(i))
                    {
                        rmd.colNullable[i] = e.nullability;
                        rmd.isIdentity[i] = e.isIdentity;
                        rmd.isWritable[i] = e.isWritable;
                    }

                    rmd.classNames[i] = e.getValueClassName();
                }
            }

            // selected columns
            checkAggregateOrGroupByColumns(0, iResultLen);

            // having columns
            checkAggregateOrGroupByColumns(groupByEnd, orderByStart);

            // order by columns
            checkAggregateOrGroupByOrderColumns(orderByStart, orderByEnd);
            prepareSort();

            simpleLimit = (isDistinctSelect == false && isGrouped == false
                           && unionSelect == null && iOrderLen == 0);
        }

        /**
         * This is called externally only on the first Select _in a UNION chain.
         */
        public void prepareUnions()
        {

            int count = 0;

            for (Select current = this; current != null;
                    current = current.unionSelect, count++) { }

            if (count == 1)
            {
                if (unionDepth != 0)
                {
                    throw Trace.error(Trace.MISSING_CLOSEBRACKET);
                }

                return;
            }

            unionArray = new Select[count];
            count = 0;

            for (Select current = this; current != null;
                    current = current.unionSelect, count++)
            {
                unionArray[count] = current;
                unionMaxDepth = current.unionDepth > unionMaxDepth
                                ? current.unionDepth
                                : unionMaxDepth;
            }

            if (unionArray[unionArray.Length - 1].unionDepth != 0)
            {
                throw Trace.error(Trace.MISSING_CLOSEBRACKET);
            }
        }

        /**
         * Returns the result of executing this Select.
         *
         * @param maxrows may be 0 to indicate no limit on the number of rows.
         * Positive values limit the size of the result set.
         * @return the result of executing this Select
         * @  if a database access error occurs
         */
        public Result getResult(Session session, int maxrows)
        {

            Result r;

            if (unionArray == null)
            {
                r = getSingleResult(session, maxrows);
            }
            else
            {
                r = getResultMain(session);

                if (sortUnion)
                {
                    sortResult(session, r);
                    r.trimResult(getLimitStart(session),
                                 getLimitCount(session, maxrows));
                }
            }

            // fredt - now there is no need for the sort and group columns
            r.setColumnCount(iResultLen);

            return r;
        }

        private Result getResultMain(Session session)
        {

            Result[] unionResults = new Result[unionArray.Length];

            for (int i = 0; i < unionArray.Length; i++)
            {
                unionResults[i] = unionArray[i].getSingleResult(session,
                        int.MaxValue);
            }

            for (int depth = unionMaxDepth; depth >= 0; depth--)
            {
                for (int pass = 0; pass < 2; pass++)
                {
                    for (int i = 0; i < unionArray.Length - 1; i++)
                    {
                        if (unionResults[i] != null
                                && unionArray[i].unionDepth >= depth)
                        {
                            if (pass == 0
                                    && unionArray[i].unionType
                                       != Select.INTERSECT)
                            {
                                continue;
                            }

                            if (pass == 1
                                    && unionArray[i].unionType
                                       == Select.INTERSECT)
                            {
                                continue;
                            }

                            int nextIndex = i + 1;

                            for (; nextIndex < unionArray.Length; nextIndex++)
                            {
                                if (unionResults[nextIndex] != null)
                                {
                                    break;
                                }
                            }

                            if (nextIndex == unionArray.Length)
                            {
                                break;
                            }

                            unionArray[i].mergeResults(session, unionResults[i],
                                                       unionResults[nextIndex]);

                            unionResults[nextIndex] = unionResults[i];
                            unionResults[i] = null;
                        }
                    }
                }
            }

            return unionResults[unionResults.Length - 1];
        }

        /**
         * Merges the second result into the first using the unionMode
         * set operation.
         */
        private void mergeResults(Session session, Result first,
                                  Result second)
        {

            switch (unionType)
            {

                case UNION:
                    first.append(second);
                    first.removeDuplicates(session, iResultLen);
                    break;

                case UNIONALL:
                    first.append(second);
                    break;

                case INTERSECT:
                    first.removeDifferent(session, second, iResultLen);
                    break;

                case EXCEPT:
                    first.removeSecond(session, second, iResultLen);
                    break;
            }
        }

        int getLimitStart(Session session)
        {

            if (limitCondition != null)
            {
                object limit =
                    limitCondition.getArg().getValue(session);

                if (limit != null)
                {
                    return (int)limit;
                }
            }

            return 0;
        }

        /**
         * For SELECT LIMIT n m ....
         * finds cases where the result does not have to be fully built and
         * returns an adjusted rowCount with LIMIT params.
         */
        int getLimitCount(Session session, int rowCount)
        {

            int limitCount = 0;

            if (limitCondition != null)
            {
       
                object limit =     limitCondition.getArg2().getValue(session);

                if (limit != null)
                {
                    limitCount = (int) limit;
                }
            }

            if (rowCount != 0 && (limitCount == 0 || rowCount < limitCount))
            {
                limitCount = rowCount;
            }

            return limitCount;
        }

        /**
         * translate the rowCount into total number of rows needed from query,
         * including any rows skipped at the beginning
         */
        int getMaxRowCount(Session session, int rowCount)
        {

            int limitStart = getLimitStart(session);
            int limitCount = getLimitCount(session, rowCount);

            if (!simpleLimit)
            {
                rowCount = int.MaxValue;
            }
            else
            {
                if (rowCount == 0)
                {
                    rowCount = limitCount;
                }

                if (rowCount == 0 || rowCount > int.MaxValue - limitStart)
                {
                    rowCount = int.MaxValue;
                }
                else
                {
                    rowCount += limitStart;
                }
            }

            return rowCount;
        }

        private Result getSingleResult(Session session,
                                       int rowCount)
        {

            if (resultMetaData == null)
            {
                prepareResult(session);
            }

            Result r = buildResult(session, getMaxRowCount(session, rowCount));

            // the result is perhaps wider (due to group and order by)
            // so use the visible columns to remove duplicates
            if (isDistinctSelect)
            {
                r.removeDuplicates(session, iResultLen);
            }

            if (!sortUnion)
            {
                sortResult(session, r);
                r.trimResult(getLimitStart(session),
                             getLimitCount(session, rowCount));
            }

            return r;
        }

        private void prepareSort()
        {

            if (iOrderLen == 0)
            {
                return;
            }

            sortOrder = new int[iOrderLen];
            sortDirection = new int[iOrderLen];

            int startCol = iResultLen + iGroupLen + iHavingLen;

            for (int i = startCol, j = 0; j < iOrderLen; i++, j++)
            {
                int colindex = i;

                // fredt - when a union, use the visible select columns for sort comparison
                // also whenever a column alias is used
                if (exprColumns[i].joinedTableColumnIndex != -1)
                {
                    colindex = exprColumns[i].joinedTableColumnIndex;
                }

                sortOrder[j] = colindex;
                sortDirection[j] = exprColumns[i].isDescending() ? -1
                                                                 : 1;
            }
        }

        private void sortResult(Session session, Result r)
        {

            if (iOrderLen == 0)
            {
                return;
            }

            r.sortResult(session, sortOrder, sortDirection);
        }

        /**
         * Check result columns for aggregate or group by violation.
         * If any result column is aggregated, then all result columns need to be
         * aggregated, unless it is included _in the group by clause.
         */
        private void checkAggregateOrGroupByColumns(int start,
                int end)
        {

            if (start < end)
            {
                List<Expression> colExps = new List<Expression>();

                for (int i = start; i < end; i++)
                {
                    exprColumns[i].collectInGroupByExpressions(colExps);
                }

                foreach (var exp in colExps)
                {
                  
                    if (inAggregateOrGroupByClause(exp))
                    {
                        continue;
                    }

                    throw Trace.error(Trace.NOT_IN_AGGREGATE_OR_GROUP_BY, exp);
                }
            }
        }

        private void checkAggregateOrGroupByOrderColumns(int start,
                int end)
        {

            checkAggregateOrGroupByColumns(start, end);

            if (start < end && isDistinctSelect)
            {
                List<Expression> colExps = new List<Expression>();

                for (int i = start; i < end; i++)
                {
                    exprColumns[i].collectInGroupByExpressions(colExps);
                }

                foreach (var exp in colExps)
                {
                    if (isSimilarIn(exp, 0, iResultLen))
                    {
                        continue;
                    }

                    throw Trace.error(Trace.INVALID_ORDER_BY_IN_DISTINCT_SELECT,
                                      exp);
                }
            }
        }

        /**
         * Check if the given expression is acceptable _in a select that may
         * include aggregate function and/or group by clause.
         * <p>
         * The expression is acceptable if:
         * <UL>
         * <LI>The select does not containt any aggregate function;
         * <LI>The expression itself can be included _in an aggregate select;
         * <LI>The expression is defined _in the group by clause;
         * <LI>All the columns _in the expression are defined _in the group by clause;
         * </UL)
         */
        private bool inAggregateOrGroupByClause(Expression exp)
        {

            if (isGrouped)
            {
                return isSimilarIn(exp, iResultLen, iResultLen + iGroupLen)
                       || allColumnsAreDefinedIn(exp, groupColumnNames);
            }
            else if (isAggregated)
            {
                return exp.canBeInAggregate();
            }
            else
            {
                return true;
            }
        }

        /**
         * Check if the given expression is similar to any of the eColumn
         * expressions within the given range.
         */
        private bool isSimilarIn(Expression exp, int start, int end)
        {

            for (int i = start; i < end; i++)
            {
                if (exp.similarTo(exprColumns[i]))
                {
                    return true;
                }
            }

            return false;
        }

        /**
         * Check if all the column names used _in the given expression are defined
         * _in the given defined column names.
         */
        static bool allColumnsAreDefinedIn(Expression exp,
                                              HashSet<string> definedColumns)
        {

            HashSet<string> colNames = new HashSet<string>();

            exp.collectAllColumnNames(colNames);

            if ((colNames.Count > 0) && (definedColumns == null))
            {
                return false;
            }           

            foreach (var n in colNames)
            {
                if (!definedColumns.Contains(n))
                {
                    return false;
                }
            }

            return true;
        }

        // fredt@users 20030810 - patch 1.7.2 - OUTER JOIN rewrite
        private Result buildResult(Session session,
                                   int limitcount)
        {

            GroupedResult gResult = new GroupedResult(this, resultMetaData);
            int len = exprColumns.Length;
            int filter = tFilter.Length;
            bool[] first = new bool[filter];
            bool[] outerused = new bool[filter];
            int level = 0;

            // fredt - shortcut needed by OpenOffice to speed up empty query processing for metadata
            bool notempty = !(queryCondition != null
                                 && queryCondition.isFixedConditional()
                                 && !queryCondition.testCondition(session));

            while (notempty && level >= 0)
            {

                // perform a join
                TableFilter t = tFilter[level];
                bool found;
                bool outerfound;

                if (!first[level])
                {
                    found = t.findFirst(session);

                    // if outer join, and no inner result, get next outer row
                    // nonJoinIsNull disallows getting the next outer row _in some circumstances
                    outerused[level] = outerfound = t.isOuterJoin && !found
                                                    && !outerused[level]
                                                    && !t.nonJoinIsNull
                                                    && t.nextOuter(session);
                    first[level] = found;
                }
                else
                {
                    found = t.next(session);
                    outerused[level] = outerfound = t.isOuterJoin && !found
                                                    && !first[level]
                                                    && !outerused[level]
                                                    && !t.nonJoinIsNull
                                                    && t.nextOuter(session);
                    first[level] = found;
                }

                if (!found && !outerfound)
                {
                    level--;

                    continue;
                }

                if (level < filter - 1)
                {
                    level++;

                    continue;
                }
                else
                {
                    while (outerused[level])
                    {
                        outerused[level--] = false;
                    }
                }

                // apply condition
                if (queryCondition == null
                        || queryCondition.testCondition(session))
                {
                    try
                    {
                        Object[] row = new Object[len];

                        // gets the group by column values first.
                        for (int i = gResult.groupBegin; i < gResult.groupEnd;
                                i++)
                        {
                            row[i] = exprColumns[i].getValue(session);
                        }

                        row = gResult.getRow(row);

                        // Get all other values
                        for (int i = 0; i < gResult.groupBegin; i++)
                        {
                            row[i] =
                                isAggregated && exprColumns[i].isAggregate()
                                ? exprColumns[i].updateAggregatingValue(session,
                                    row[i])
                                : exprColumns[i].getValue(session);
                        }

                        for (int i = gResult.groupEnd; i < len; i++)
                        {
                            row[i] =
                                isAggregated && exprColumns[i].isAggregate()
                                ? exprColumns[i].updateAggregatingValue(session,
                                    row[i])
                                : exprColumns[i].getValue(session);
                        }

                        gResult.addRow(row);

                        if (gResult.size() >= limitcount)
                        {
                            break;
                        }
                    }
                    catch (HsqlInternalException)
                    {
                        continue;
                    }
                }
            }

            if (isAggregated && !isGrouped && gResult.size() == 0)
            {
                Object[] row = new Object[len];

                for (int i = 0; i < len; i++)
                {
                    row[i] = exprColumns[i].isAggregate() ? null
                                                          : exprColumns[i]
                                                          .getValue(session);
                }

                gResult.addRow(row);
            }

            Iterator it = gResult.iterator();

            while (it.hasNext())
            {
                Object[] row = (Object[])it.next();

                if (isAggregated)
                {
                    for (int i = 0; i < len; i++)
                    {
                        if (exprColumns[i].isAggregate())
                        {
                            row[i] = exprColumns[i].getAggregatedValue(session,
                                    row[i]);
                        }
                    }
                }

                if (iHavingLen > 0)
                {

                    // The test value, either aggregate or not, is set already.
                    // Removes the row that does not satisfy the HAVING
                    // condition.
                    if (!true.Equals(row[iResultLen + iGroupLen]))
                    {
                        it.remove();
                    }
                }
            }

            return gResult.getResult();
        }

        /**
         * Skeleton under development. Needs a lot of work.
         */
        public StringBuilder getDDL()
        {

            StringBuilder sb = new StringBuilder();

            sb.Append(Token.T_SELECT).Append(' ');

            //limitStart;
            //limitCount;
            for (int i = 0; i < iResultLen; i++)
            {
                sb.Append(exprColumns[i].getDDL());

                if (i < iResultLen - 1)
                {
                    sb.Append(',');
                }
            }

            sb.Append(Token.T_FROM);

            for (int i = 0; i < tFilter.Length; i++)
            {

                // find _out if any expression _in any of the filters isInJoin then use this form
                TableFilter filter = tFilter[i];

                // if any expression isInJoin
                if (i != 0)
                {
                    if (filter.isOuterJoin)
                    {
                        sb.Append(Token.T_FROM).Append(' ');
                        sb.Append(Token.T_JOIN).Append(' ');
                    }

                    // eStart and eEnd expressions
                }

                // otherwise use a comma delimited table list
                sb.Append(',');
            }

            // if there are any expressions that are not isInJoin
            sb.Append(' ').Append(Token.T_WHERE).Append(' ');

            for (int i = 0; i < tFilter.Length; i++)
            {
                TableFilter filter = tFilter[i];

                // eStart and eEnd expressions that are not isInJoin
            }

            // if has GROUP BY
            sb.Append(' ').Append(Token.T_GROUP).Append(' ');

            for (int i = iResultLen; i < iResultLen + iGroupLen; i++)
            {
                sb.Append(exprColumns[i].getDDL());

                if (i < iResultLen + iGroupLen - 1)
                {
                    sb.Append(',');
                }
            }

            // if has HAVING
            sb.Append(' ').Append(Token.T_HAVING).Append(' ');

            for (int i = iResultLen + iGroupLen;
                    i < iResultLen + iGroupLen + iHavingLen; i++)
            {
                sb.Append(exprColumns[i].getDDL());

                if (i < iResultLen + iGroupLen - 1)
                {
                    sb.Append(',');
                }
            }

            if (unionSelect != null)
            {
                switch (unionType)
                {

                    case EXCEPT:
                        sb.Append(' ').Append(Token.T_EXCEPT).Append(' ');
                        break;

                    case INTERSECT:
                        sb.Append(' ').Append(Token.T_INTERSECT).Append(' ');
                        break;

                    case UNION:
                        sb.Append(' ').Append(Token.T_UNION).Append(' ');
                        break;

                    case UNIONALL:
                        sb.Append(' ').Append(Token.T_UNION).Append(' ').Append(
                            Token.T_ALL).Append(' ');
                        break;
                }
            }

            // if has ORDER BY
            int groupByEnd = iResultLen + iGroupLen;
            int orderByStart = groupByEnd + iHavingLen;
            int orderByEnd = orderByStart + iOrderLen;

            sb.Append(' ').Append(Token.T_ORDER).Append(Token.T_BY).Append(' ');

            for (int i = orderByStart; i < orderByEnd; i++)
            {
                sb.Append(exprColumns[i].getDDL());

                if (i < iResultLen + iGroupLen - 1)
                {
                    sb.Append(',');
                }
            }

            return sb;
        }

        private bool _isResolved = false;

        /**
         * @todo - post 1.8.0 - review resolve and check resolve -
         * determine if isResolved is specific to main query or the full set including UNION
         *
         */
        public bool resolveAll(Session session, bool check)
        {

            if (_isResolved)
            {
                return true;
            }

            resolve(session);

            _isResolved = checkResolved(check);

            if (unionSelect != null)
            {
                if (unionSelect.iResultLen != iResultLen)
                {
                    throw Trace.error(Trace.COLUMN_COUNT_DOES_NOT_MATCH);
                }

                for (int i = 0; i < iResultLen; i++)
                {
                    Expression e = exprColumns[i];

                    if (!e.isTypeEqual(unionSelect.exprColumns[i]))
                    {
                        unionSelect.exprColumns[i] =
                            new Expression(unionSelect.exprColumns[i],
                                           e.getDataType(), e.getColumnSize(),
                                           e.getColumnScale());
                    }
                }

                _isResolved &= unionSelect.resolveAll(session, check);
            }

            return _isResolved;
        }

        bool isResolved()
        {
            return _isResolved;
        }

        public string describe(Session session)
        {

            StringBuilder sb;
            string temp;

            // temporary :  it is currently unclear whether this may affect
            // later attempts to retrieve an actual result (calls getResult(1)
            // _in preProcess mode).  Thus, ToString() probably should not be called
            // on Select objects that will actually be used to retrieve results,
            // only on Select objects used by EXPLAIN PLAN FOR
            try
            {
                getResult(session, 1);
            }
            catch (HsqlException) { }

            sb = new StringBuilder();

            sb.Append(base.ToString()).Append("[\n");

            if (sIntoTable != null)
            {
                sb.Append("into table=[").Append(sIntoTable.name).Append("]\n");
            }

            if (limitCondition != null)
            {
                sb.Append("offset=[").Append(
                    limitCondition.getArg().describe(session)).Append("]\n");
                sb.Append("limit=[").Append(
                    limitCondition.getArg2().describe(session)).Append("]\n");
            }

            sb.Append("isDistinctSelect=[").Append(isDistinctSelect).Append(
                "]\n");
            sb.Append("isGrouped=[").Append(isGrouped).Append("]\n");
            sb.Append("isAggregated=[").Append(isAggregated).Append("]\n");
            sb.Append("columns=[");

            int columns = exprColumns.Length - iOrderLen;

            for (int i = 0; i < columns; i++)
            {
                sb.Append(exprColumns[i].describe(session));
            }

            sb.Append("\n]\n");
            sb.Append("tableFilters=[\n");

            for (int i = 0; i < tFilter.Length; i++)
            {
                sb.Append("[\n");
                sb.Append(tFilter[i].describe(session));
                sb.Append("\n]");
            }

            sb.Append("]\n");

            temp = queryCondition == null ? "null"
                                          : queryCondition.describe(session);

            sb.Append("eCondition=[").Append(temp).Append("]\n");

            temp = havingCondition == null ? "null"
                                           : havingCondition.describe(session);

            sb.Append("havingCondition=[").Append(temp).Append("]\n");
            sb.Append("groupColumns=[").Append(groupColumnNames).Append("]\n");

            if (unionSelect != null)
            {
                switch (unionType)
                {

                    case EXCEPT:
                        sb.Append(" EXCEPT ");
                        break;

                    case INTERSECT:
                        sb.Append(" INTERSECT ");
                        break;

                    case UNION:
                        sb.Append(" UNION ");
                        break;

                    case UNIONALL:
                        sb.Append(" UNION ALL ");
                        break;

                    default:
                        sb.Append(" UNKNOWN SET OPERATION ");
                        break;
                }

                sb.Append("[\n").Append(unionSelect.describe(session)).Append(
                    "]\n");
            }

            return sb.ToString();
        }

        public Result describeResult()
        {

            Result r;
            Result.ResultMetaData rmd;
            Expression e;

            r = new Result(ResultConstants.DATA, iResultLen);
            rmd = r.metaData;

            for (int i = 0; i < iResultLen; i++)
            {
                e = exprColumns[i];
                rmd.colTypes[i] = e.getDataType();
                rmd.colSizes[i] = e.getColumnSize();
                rmd.colScales[i] = e.getColumnScale();
                rmd.colLabels[i] = e.getAlias();
                rmd.isLabelQuoted[i] = e.isAliasQuoted();
                rmd.tableNames[i] = e.getTableName();
                rmd.colNames[i] = e.getColumnName();

                if (rmd.isTableColumn(i))
                {
                    rmd.colNullable[i] = e.nullability;
                    rmd.isIdentity[i] = e.isIdentity;
                    rmd.isWritable[i] = e.isWritable;
                }
            }

            return r;
        }
    }

}